﻿using System;

namespace VideoStitching
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Hello World!");
            int[,] clips = new int[,] { { 0, 2 }, { 4, 6 }, { 8, 10 }, { 1, 9 }, { 1, 5 }, { 5, 9 } };
            int[,,] aaa = new int[,,] { { { 1, 2 }, { 1, 2 } }, { { 2, 1 }, { 2, 2 } } };

            int[][] arr = new int[][]{
                new int[] { 0, 2 },
                new int[] { 4, 6 },
                new int[] { 8, 10 },
                new int[] { 1, 9 },
                new int[] { 1, 5 },
                new int[] { 5, 9 }
            };

            // foreach (var item in clips)
            // {
            //     System.Console.WriteLine(item);
            // }

            VideoStitching(arr, 10);
            // var i = clips[2,1];
        }

        static int VideoStitching(int[][] clips, int T)
        {
            int[] dp = new int[T + 1];
            Array.Fill<int>(dp, int.MaxValue - 1);
            dp[0] = 0;
            for (int i = 1; i <= T; i++)
            {
                foreach (var clip in clips)
                {
                    if (clip[0] < i && clip[1] >= i)
                    {
                        dp[i] = Math.Min(dp[i], dp[clip[0]] + 1);
                    }
                }
            }

            return (dp[T] == int.MaxValue - 1) ? -1 : dp[T];
        }

    }
}
